<html>
 <head>
  <meta charset="utf-8"/>
  <meta content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no" name="viewport"/>
  <title>
   GPU基础算法: Reduce, Scan, Histogram  | 数螺 | NAUT IDEA
  </title>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap-theme.min.css" rel="stylesheet"/>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet"/>
  <style type="text/css">
   #xmain img {
                  max-width: 100%;
                  display: block;
                  margin-top: 10px;
                  margin-bottom: 10px;
                }

                #xmain p {
                    line-height:150%;
                    font-size: 16px;
                    margin-top: 20px;
                }

                #xmain h2 {
                    font-size: 24px;
                }

                #xmain h3 {
                    font-size: 20px;
                }

                #xmain h4 {
                    font-size: 18px;
                }


                .header {
	           background-color: #0099ff;
	           color: #ffffff;
	           margin-bottom: 20px;
	        }

	        .header p {
                  margin: 0px;
                  padding: 10px 0;
                  display: inline-block;  
                  vertical-align: middle;
                  font-size: 16px;
               }

               .header a {
                 color: white;
               }

              .header img {
                 height: 25px;
              }
  </style>
  <script src="http://cdn.bootcss.com/jquery/3.0.0/jquery.min.js">
  </script>
  <script src="http://nautstatic-10007657.file.myqcloud.com/static/css/readability.min.js" type="text/javascript">
  </script>
  <script type="text/javascript">
   $(document).ready(function() {
                 var loc = document.location;
                 var uri = {
                  spec: "http://dataunion.org/19959.html",
                  host: "http://dataunion.org",
                  prePath: "http://dataunion.org",
                  scheme: "http",
                  pathBase: "http://dataunion.org/"
                 };
    
                 var documentClone = document.cloneNode(true);
                 var article = new Readability(uri, documentClone).parse();
     
                 document.getElementById("xmain").innerHTML = article.content;
                });
  </script>
  <!-- 1466454667: Accept with keywords: (title(0.25):算法,基础,数盟,社区, topn(0.3):社区,并行,复杂度,个数,数盟,深度学习,行业资讯,直方图,数据挖掘,数据分析,结果,元素,职业规划,例子,基础架构,答案,文章,可视化,方法,镜面反射,问题,算法,结合律,优化,逻辑,顺序,编程语言,部分,线程,综上).-->
 </head>
 <body onload="">
  <div class="header">
   <div class="container">
    <div class="row">
     <div class="col-xs-6 col-sm-6 text-left">
      <a href="/databee">
       <img src="http://nautidea-10007657.cos.myqcloud.com/logo_white.png"/>
      </a>
      <a href="/databee">
       <p>
        数螺
       </p>
      </a>
     </div>
     <div class="hidden-xs col-sm-6 text-right">
      <p>
       致力于数据科学的推广和知识传播
      </p>
     </div>
    </div>
   </div>
  </div>
  <div class="container text-center">
   <h1>
    GPU基础算法: Reduce, Scan, Histogram
   </h1>
  </div>
  <div class="container" id="xmain">
   ﻿﻿
   <title>
    GPU基础算法: Reduce, Scan, Histogram | 数盟社区
   </title>
   <!-- All in One SEO Pack 2.2.7.6.2 by Michael Torbert of Semper Fi Web Design[32,79] -->
   <!-- /all in one seo pack -->
   <!--
<div align="center">
<a href="http://strata.oreilly.com.cn/hadoop-big-data-cn?cmp=mp-data-confreg-home-stcn16_dataunion_pc" target="_blank"><img src="http://dataunion.org/wp-content/uploads/2016/05/stratabj.jpg"/ ></a>
</div>
-->
   <header id="header-web">
    <div class="header-main">
     <hgroup class="logo">
      <h1>
       <a href="http://dataunion.org/" rel="home" title="数盟社区">
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/logo.png"/>
       </a>
      </h1>
     </hgroup>
     <!--logo-->
     <nav class="header-nav">
      <ul class="menu" id="menu-%e4%b8%bb%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-71" id="menu-item-71">
        <a href="http://dataunion.org/category/events" title="events">
         活动
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22457" id="menu-item-22457">
          <a href="http://dataunion.org/2016timeline">
           2016档期
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22459" id="menu-item-22459">
          <a href="http://dataunion.org/category/parterc">
           合作会议
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor current-menu-parent current-post-parent menu-item-has-children menu-item-20869" id="menu-item-20869">
        <a href="http://dataunion.org/category/tech" title="articles">
         文章
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20867" id="menu-item-20867">
          <a href="http://dataunion.org/category/tech/base" title="base">
           基础架构
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3302" id="menu-item-3302">
          <a href="http://dataunion.org/category/tech/ai" title="ai">
           人工智能
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3303" id="menu-item-3303">
          <a href="http://dataunion.org/category/tech/analysis" title="analysis">
           数据分析
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21920" id="menu-item-21920">
          <a href="http://dataunion.org/category/tech/dm">
           数据挖掘
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3314" id="menu-item-3314">
          <a href="http://dataunion.org/category/tech/viz" title="viz">
           可视化
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3305" id="menu-item-3305">
          <a href="http://dataunion.org/category/tech/devl" title="devl">
           编程语言
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-20876" id="menu-item-20876">
        <a href="http://dataunion.org/category/industry">
         行业
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-16328" id="menu-item-16328">
          <a href="http://dataunion.org/category/industry/case" title="case">
           行业应用
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-2112" id="menu-item-2112">
          <a href="http://dataunion.org/category/industry/demo" title="demo">
           Demo展示
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21562" id="menu-item-21562">
          <a href="http://dataunion.org/category/industry/news">
           行业资讯
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-311" id="menu-item-311">
        <a href="http://dataunion.org/category/sources" title="sources">
         资源
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20870" id="menu-item-20870">
        <a href="http://dataunion.org/category/books" title="book">
         图书
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21363" id="menu-item-21363">
        <a href="http://dataunion.org/category/training">
         课程
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-21853" id="menu-item-21853">
        <a href="http://dataunion.org/category/jobs">
         职位
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22050" id="menu-item-22050">
          <a href="http://dataunion.org/category/career">
           职业规划
          </a>
         </li>
        </ul>
       </li>
      </ul>
     </nav>
     <!--header-nav-->
    </div>
   </header>
   <!--header-web-->
   <div id="main">
    <div id="soutab">
     <form action="http://dataunion.org/" class="search" method="get">
     </form>
    </div>
    <div id="container">
     <nav id="mbx">
      当前位置：
      <a href="http://dataunion.org">
       首页
      </a>
      &gt;
      <a href="http://dataunion.org/category/tech">
       文章
      </a>
      &gt;  正文
     </nav>
     <!--mbx-->
     <article class="content">
      <header align="centre" class="contenttitle">
       <div class="mscc">
        <h1 class="mscctitle">
         <a href="http://dataunion.org/19959.html">
          GPU基础算法: Reduce, Scan, Histogram
         </a>
        </h1>
        <address class="msccaddress ">
         <em>
          1,845 次阅读 -
         </em>
         <a href="http://dataunion.org/category/tech" rel="category tag">
          文章
         </a>
        </address>
       </div>
      </header>
      <div class="content-text">
       <p>
        作者：
        <a class="user_name" href="http://my.csdn.net/abcjennifer" target="_blank">
         Rachel-Zhang
        </a>
        出处：
        <a href="http://blog.csdn.net/abcjennifer/article/details/43528407">
         Rachel-Zhang的博客
        </a>
       </p>
       <p>
        GPU算法：reduce，scan，histogram，它们在并行算法中非常常用，我们在本文中分别就其功能用处，串行与并行实现进行阐述。
       </p>
       <h2 id="1-task-complexity">
        <p name="t0">
        </p>
        1. Task complexity
       </h2>
       <p>
        task complexity包括step complexity（可以并行成几个操作） &amp; work complexity（总共有多少个工作要做）。
        <br/>
        e.g. 下面的tree-structure图中每个节点表示一个操作数，每条边表示一个操作，同层edge表示相同操作，问该图表示的task的step complexity &amp; work complexity分别是多少。
       </p>
       <p>
        <img src="http://img.blog.csdn.net/20150213152710238"/>
       </p>
       <p>
        Ans:
        <br/>
        step complexity: 3；
        <br/>
        work complexity: 6。
        <br/>
        下面会有更具体的例子。
       </p>
       <hr/>
       <p>
       </p>
       <h2 id="2-reduce">
        <p name="t1">
        </p>
        2. Reduce
       </h2>
       <p>
        引入：我们考虑一个task：1+2+3+4+…
        <br/>
        1) 最简单的顺序执行顺序组织为((1+2)+3)+4…
        <br/>
        2) 由于operation之间没有依赖关系，我们可以用Reduce简化操作，它可以减少serial implementation的步数。
       </p>
       <h3 id="21-what-is-reduce">
        <p name="t2">
        </p>
        2.1 what is reduce?
       </h3>
       <p>
        Reduce input:
       </p>
       <ol>
        <li>
         set of elements
        </li>
        <li>
         reduction operation
         <ol>
          <li>
           binary: 两个输入一个输出
          </li>
          <li>
           操作满足结合律： (a@b)@c = a@(b@c), 其中@表示operator
           <br/>
           e.g +, 按位与 都符合；a^b(expotentiation)和减法都不是
          </li>
         </ol>
        </li>
       </ol>
       <p>
        <img src="http://img.blog.csdn.net/20150213145544805"/>
       </p>
       <h3 id="211-serial-implementation-of-reduce">
        <p name="t3">
        </p>
        2.1.1 Serial implementation of Reduce:
       </h3>
       <p>
        reduce的每一步操作都依赖于其前一个操作的结果。比如对于前面那个例子，n个数相加，work complexity 和 step complexity都是O(n)（原因不言自明吧~）我们的目标就是并行化操作，降下来step complexity. e.g add serial reduce -&gt; parallel reduce。
       </p>
       <h3 id="212-parallel-implementation-of-reduce">
        <p name="t4">
        </p>
        2.1.2 Parallel implementation of Reduce:
       </h3>
       <p>
        <img src="http://img.blog.csdn.net/20150213145641025"/>
       </p>
       <p>
        也就是说，我们把step complexity降到了
        <span class="MathJax" id="MathJax-Element-38-Frame">
         <span class="math" id="MathJax-Span-1">
          <span class="mrow" id="MathJax-Span-2">
           <span class="mi" id="MathJax-Span-3">
            l
           </span>
           <span class="mi" id="MathJax-Span-4">
            o
           </span>
           <span class="msubsup" id="MathJax-Span-5">
            <span class="mi" id="MathJax-Span-6">
             g
            </span>
            <span class="mn" id="MathJax-Span-7">
             2
            </span>
           </span>
           <span class="mi" id="MathJax-Span-8">
            n
           </span>
          </span>
         </span>
        </span>
       </p>
       <p>
        举个栗子，如下图所示：
        <br/>
        <img src="http://img.blog.csdn.net/20150625092301326"/>
       </p>
       <p>
        那么如果对
        <span class="MathJax" id="MathJax-Element-39-Frame">
         <span class="math" id="MathJax-Span-9">
          <span class="mrow" id="MathJax-Span-10">
           <span class="msubsup" id="MathJax-Span-11">
            <span class="mn" id="MathJax-Span-12">
             2
            </span>
            <span class="texatom" id="MathJax-Span-13">
             <span class="mrow" id="MathJax-Span-14">
              <span class="mn" id="MathJax-Span-15">
               10
              </span>
             </span>
            </span>
           </span>
          </span>
         </span>
        </span>
        个数做parallel reduce add，其step complexity就是10. 那么在这个parallel reduce的第一步，我们需要做512个加法，这对modern gpu不是啥大问题，但是如果我们要对
        <span class="MathJax" id="MathJax-Element-40-Frame">
         <span class="math" id="MathJax-Span-16">
          <span class="mrow" id="MathJax-Span-17">
           <span class="msubsup" id="MathJax-Span-18">
            <span class="mn" id="MathJax-Span-19">
             2
            </span>
            <span class="texatom" id="MathJax-Span-20">
             <span class="mrow" id="MathJax-Span-21">
              <span class="mn" id="MathJax-Span-22">
               20
              </span>
             </span>
            </span>
           </span>
          </span>
         </span>
        </span>
        个数做加法呢？就需要考虑到gpu数量了，如果说gpu最多能并行做512个操作，我们就应将
        <span class="MathJax" id="MathJax-Element-41-Frame">
         <span class="math" id="MathJax-Span-23">
          <span class="mrow" id="MathJax-Span-24">
           <span class="msubsup" id="MathJax-Span-25">
            <span class="mn" id="MathJax-Span-26">
             2
            </span>
            <span class="texatom" id="MathJax-Span-27">
             <span class="mrow" id="MathJax-Span-28">
              <span class="mn" id="MathJax-Span-29">
               20
              </span>
             </span>
            </span>
           </span>
          </span>
         </span>
        </span>
        个数分成1024*1024(共1024组)，每次做
        <span class="MathJax" id="MathJax-Element-42-Frame">
         <span class="math" id="MathJax-Span-30">
          <span class="mrow" id="MathJax-Span-31">
           <span class="msubsup" id="MathJax-Span-32">
            <span class="mn" id="MathJax-Span-33">
             2
            </span>
            <span class="texatom" id="MathJax-Span-34">
             <span class="mrow" id="MathJax-Span-35">
              <span class="mn" id="MathJax-Span-36">
               10
              </span>
             </span>
            </span>
           </span>
          </span>
         </span>
        </span>
        个数的加法。这种考虑task规模和gpu数量关系的做法有个理论叫Brent’s Theory. 下面我们具体来看：
       </p>
       <p>
        <img src="http://img.blog.csdn.net/20150213145804704"/>
       </p>
       <p>
        也就是进行两步操作，第一步分成1024个block，每个block做加法；第二步将这1024个结果再用1个1024个thread的block进行求和。kernel code：
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7225103095724" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          __global__ &lt;span class="hljs-keyword"&gt;void&lt;/span&gt; parallel_reduce_kernel(&lt;span class="hljs-keyword"&gt;float&lt;/span&gt; *d_out, &lt;span class="hljs-keyword"&gt;float&lt;/span&gt;* d_in){
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; myID = threadIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt; + blockIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt; * blockDim&lt;span class="hljs-variable"&gt;.x&lt;/span&gt;;
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; tid = threadIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt;;

    &lt;span class="hljs-comment"&gt;//divide threads into two parts according to threadID, and add the right part to the left one, lead to reducing half elements, called an iteration; iterate until left only one element&lt;/span&gt;
    &lt;span class="hljs-keyword"&gt;for&lt;/span&gt;(&lt;span class="hljs-keyword"&gt;unsigned&lt;/span&gt; &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; s = blockDim&lt;span class="hljs-variable"&gt;.x&lt;/span&gt; / &lt;span class="hljs-number"&gt;2&lt;/span&gt; ; s&amp;gt;&lt;span class="hljs-number"&gt;0&lt;/span&gt;; s&amp;gt;&amp;gt;=&lt;span class="hljs-number"&gt;1&lt;/span&gt;){
        &lt;span class="hljs-keyword"&gt;if&lt;/span&gt;(tid&amp;lt;s){
            d_in[myID] += d_in[myID + s];
        }
        __syncthreads(); &lt;span class="hljs-comment"&gt;//ensure all adds at one iteration are done&lt;/span&gt;
    }
    &lt;span class="hljs-keyword"&gt;if&lt;/span&gt; (tid == &lt;span class="hljs-number"&gt;0&lt;/span&gt;){
        d_out[blockIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt;] = d_in[myId];
    }
}
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-1">
               1
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-2">
               2
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-3">
               3
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-4">
               4
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-5">
               5
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-6">
               6
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-7">
               7
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-8">
               8
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-9">
               9
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-10">
               10
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-11">
               11
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-12">
               12
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-13">
               13
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7225103095724-14">
               14
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7225103095724-15">
               15
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7225103095724-1">
               <span class="crayon-v">
                __global__
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                void
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                parallel_reduce_kernel
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                float
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-v">
                d_out
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                float
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-2">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threadIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockDim
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-3">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threadIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-4">
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-5">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-comment"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-c">
                //divide threads into two parts according to threadID, and add the right part to the left one, lead to reducing half elements, called an iteration; iterate until left only one element&lt;/span&gt;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-6">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                for
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                unsigned
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockDim
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                2
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                1
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-7">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                if
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-8">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +=
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-9">
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                }
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-10">
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                __syncthreads
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-comment"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-c">
                //ensure all adds at one iteration are done&lt;/span&gt;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-11">
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                }
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-12">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                if
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                ==
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-13">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_out
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                blockIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myId
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7225103095724-14">
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                }
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7225103095724-15">
               <span class="crayon-sy">
                }
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0127 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
        <li>
         2
        </li>
        <li>
         3
        </li>
        <li>
         4
        </li>
        <li>
         5
        </li>
        <li>
         6
        </li>
        <li>
         7
        </li>
        <li>
         8
        </li>
        <li>
         9
        </li>
        <li>
         10
        </li>
        <li>
         11
        </li>
        <li>
         12
        </li>
        <li>
         13
        </li>
        <li>
         14
        </li>
        <li>
         15
        </li>
       </ul>
       <p>
       </p>
       <p>
        Quiz: 看一下上面的code可以从哪里进行优化？
       </p>
       <p>
        Ans：我们在上一讲中提到了global，shared &amp; local memory的速度，那么这里对于global memory的操作可以更改为shared memory，从而进行提速：
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7238729000089" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          __global__ &lt;span class="hljs-keyword"&gt;void&lt;/span&gt; parallel_shared_reduce_kernel(&lt;span class="hljs-keyword"&gt;float&lt;/span&gt; *d_out, &lt;span class="hljs-keyword"&gt;float&lt;/span&gt;* d_in){
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; myID = threadIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt; + blockIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt; * blockDim&lt;span class="hljs-variable"&gt;.x&lt;/span&gt;;
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; tid = threadIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt;;
    &lt;span class="hljs-keyword"&gt;extern&lt;/span&gt; __shared__ &lt;span class="hljs-keyword"&gt;float&lt;/span&gt; sdata[];
    sdata[tid] = d_in[myID];
    __syncthreads();

    &lt;span class="hljs-comment"&gt;//divide threads into two parts according to threadID, and add the right part to the left one, lead to reducing half elements, called an iteration; iterate until left only one element&lt;/span&gt;
    &lt;span class="hljs-keyword"&gt;for&lt;/span&gt;(&lt;span class="hljs-keyword"&gt;unsigned&lt;/span&gt; &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; s = blockDim&lt;span class="hljs-variable"&gt;.x&lt;/span&gt; / &lt;span class="hljs-number"&gt;2&lt;/span&gt; ; s&amp;gt;&lt;span class="hljs-number"&gt;0&lt;/span&gt;; s&amp;gt;&amp;gt;=&lt;span class="hljs-number"&gt;1&lt;/span&gt;){
        &lt;span class="hljs-keyword"&gt;if&lt;/span&gt;(tid&amp;lt;s){
            sdata[tid] += sdata[tid + s];
        }
        __syncthreads(); &lt;span class="hljs-comment"&gt;//ensure all adds at one iteration are done&lt;/span&gt;
    }
    &lt;span class="hljs-keyword"&gt;if&lt;/span&gt; (tid == &lt;span class="hljs-number"&gt;0&lt;/span&gt;){
        d_out[blockIdx&lt;span class="hljs-variable"&gt;.x&lt;/span&gt;] = sdata[myId];
    }
}
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-1">
               1
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-2">
               2
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-3">
               3
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-4">
               4
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-5">
               5
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-6">
               6
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-7">
               7
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-8">
               8
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-9">
               9
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-10">
               10
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-11">
               11
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-12">
               12
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-13">
               13
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-14">
               14
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-15">
               15
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-16">
               16
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7238729000089-17">
               17
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7238729000089-18">
               18
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7238729000089-1">
               <span class="crayon-v">
                __global__
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                void
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                parallel_shared_reduce_kernel
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                float
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-v">
                d_out
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                float
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-2">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threadIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockDim
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-3">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threadIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-4">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                extern
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                __shared__
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                float
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                sdata
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-5">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                sdata
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-6">
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                __syncthreads
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-7">
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-8">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-comment"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-c">
                //divide threads into two parts according to threadID, and add the right part to the left one, lead to reducing half elements, called an iteration; iterate until left only one element&lt;/span&gt;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-9">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                for
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                unsigned
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockDim
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                2
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                1
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-10">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                if
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-11">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                sdata
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +=
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                sdata
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                s
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-12">
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                }
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-13">
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                __syncthreads
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-comment"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-c">
                //ensure all adds at one iteration are done&lt;/span&gt;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-14">
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                }
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-15">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                if
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-v">
                tid
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                ==
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-16">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_out
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                blockIdx
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                sdata
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myId
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7238729000089-17">
               <span class="crayon-h">
               </span>
               <span class="crayon-sy">
                }
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7238729000089-18">
               <span class="crayon-sy">
                }
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0150 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
        <li>
         2
        </li>
        <li>
         3
        </li>
        <li>
         4
        </li>
        <li>
         5
        </li>
        <li>
         6
        </li>
        <li>
         7
        </li>
        <li>
         8
        </li>
        <li>
         9
        </li>
        <li>
         10
        </li>
        <li>
         11
        </li>
        <li>
         12
        </li>
        <li>
         13
        </li>
        <li>
         14
        </li>
        <li>
         15
        </li>
        <li>
         16
        </li>
        <li>
         17
        </li>
        <li>
         18
        </li>
       </ul>
       <p>
        优化的代码中还有一点要注意，就是声明的时候记得我们第三讲中说过的kernel通用表示形式：
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7242900311401" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          kernel&amp;lt;&amp;lt;&amp;lt;grid &lt;span class="hljs-keyword"&gt;of&lt;/span&gt; blocks, &lt;span class="hljs-keyword"&gt;block&lt;/span&gt; &lt;span class="hljs-keyword"&gt;of&lt;/span&gt; threads, shmem&amp;gt;&amp;gt;&amp;gt;
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7242900311401-1">
               1
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7242900311401-1">
               <span class="crayon-v">
                kernel
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-v">
                grid
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                of
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blocks
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                block
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                of
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threads
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                shmem
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0026 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
       </ul>
       <p>
        最后一项要在call kernel的时候声明好，即:
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7248184873796" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          parallel_reduce_kernel&amp;lt;&amp;lt;&amp;lt;blocks, threads, threads*&lt;span class="hljs-keyword"&gt;sizeof&lt;/span&gt;(&lt;span class="hljs-keyword"&gt;float&lt;/span&gt;)&amp;gt;&amp;gt;&amp;gt;(data_out, data_in);
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7248184873796-1">
               1
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7248184873796-1">
               <span class="crayon-v">
                parallel_reduce_kernel
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-v">
                blocks
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threads
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-e ">
                threads*
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                sizeof
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                float
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                gt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-v">
                data_out
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                data_in
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0023 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
       </ul>
       <p>
        好，那么问题来了，对于这两个版本（parallel_reduce_kernel 和 parallel_shared_reduce_kernel）, parallel_reduce_kernel比parallel_shared_reduce_kernel多用了几倍的global memory带宽？ Ans: 分别考虑两个版本的读写操作：
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b724e851288097" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          parallel_reduce_kernel
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b724e851288097-1">
               1
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b724e851288097-1">
               <span class="crayon-v">
                parallel_reduce_kernel
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0003 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
       </ul>
       <div align="center">
        <table>
         <tbody>
          <tr>
           <td>
            Times
           </td>
           <td>
            Read Ops
           </td>
           <td>
            Write Ops
           </td>
          </tr>
          <tr>
           <td>
            1
           </td>
           <td>
            1024
           </td>
           <td>
            512
           </td>
          </tr>
          <tr>
           <td>
            2
           </td>
           <td>
            512
           </td>
           <td>
            256
           </td>
          </tr>
          <tr>
           <td>
            3
           </td>
           <td>
            256
           </td>
           <td>
            128
           </td>
          </tr>
          <tr>
           <td>
            …
           </td>
           <td>
           </td>
           <td>
           </td>
          </tr>
          <tr>
           <td>
            n
           </td>
           <td>
            1
           </td>
           <td>
            1
           </td>
          </tr>
         </tbody>
        </table>
       </div>
       <p>
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7255605211058" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          parallel_shared_reduce_kernel
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7255605211058-1">
               1
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7255605211058-1">
               <span class="crayon-v">
                parallel_shared_reduce_kernel
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0004 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
       </ul>
       <div align="center">
        <table>
         <tbody>
          <tr>
           <td>
            Times
           </td>
           <td>
            Read Ops
           </td>
           <td>
            Write Ops
           </td>
          </tr>
          <tr>
           <td>
            1
           </td>
           <td>
            1024
           </td>
           <td>
            1
           </td>
          </tr>
         </tbody>
        </table>
       </div>
       <p>
        所以，
        <strong>
         parallel_reduce_kernel所需的带宽是parallel_shared_reduce_kernel的3倍
        </strong>
        。
       </p>
       <hr/>
       <h2 id="3-scan">
        <p name="t5">
        </p>
        3. Scan
       </h2>
       <h3 id="31-what-is-scan">
        <p name="t6">
        </p>
        3.1 what is scan?
       </h3>
       <ul>
        <li>
         Example:
         <ul>
          <li>
           input: 1,2,3,4
          </li>
          <li>
           operation: Add
          </li>
          <li>
           ouput: 1,3,6,10（out[i]=sum(in[0:i])）
          </li>
         </ul>
        </li>
        <li>
         目的：解决难以并行的问题
        </li>
       </ul>
       <p>
        拍拍脑袋想想上面这个问题O(n)的一个解法是out[i] = out[i-1] + in[i].下面我们来引入scan。
       </p>
       <p>
        Inputs to scan:
       </p>
       <ol>
        <li>
         input array
        </li>
        <li>
         操作：binary &amp; 满足结合律（和reduce一样）
        </li>
        <li>
         identity element
         <strong>
          <em>
           [I op a = a]
          </em>
         </strong>
         , 其中I 是identity element
         <br/>
         quiz: what is the identity for 加法，乘法，逻辑与，逻辑或？
         <br/>
         Ans：
        </li>
       </ol>
       <table align="center">
        <tbody>
         <tr>
          <td>
           op
          </td>
          <td>
           Identity
          </td>
         </tr>
         <tr>
          <td>
           加法
          </td>
          <td>
           0
          </td>
         </tr>
         <tr>
          <td>
           乘法
          </td>
          <td>
           1
          </td>
         </tr>
         <tr>
          <td>
           逻辑或||
          </td>
          <td>
           False
          </td>
         </tr>
         <tr>
          <td>
           逻辑与&amp;&amp;
          </td>
          <td>
           True
          </td>
         </tr>
        </tbody>
       </table>
       <p>
       </p>
       <h3 id="32-what-scan-does">
        <p name="t7">
        </p>
        3.2 what scan does?
       </h3>
       <table>
        <thead>
         <tr>
          <th>
           I/O
          </th>
          <th align="center">
           content
          </th>
          <th align="right">
          </th>
          <th align="right">
          </th>
          <th align="right">
          </th>
          <th align="right">
          </th>
         </tr>
        </thead>
        <tbody>
         <tr>
          <td>
           input
          </td>
          <td align="center">
           [
           <span class="MathJax" id="MathJax-Element-6-Frame">
            <span class="math" id="MathJax-Span-37">
             <span class="mrow" id="MathJax-Span-38">
              <span class="msubsup" id="MathJax-Span-39">
               <span class="mi" id="MathJax-Span-40">
                a
               </span>
               <span class="mn" id="MathJax-Span-41">
                0
               </span>
              </span>
             </span>
            </span>
           </span>
          </td>
          <td align="right">
           <span class="MathJax" id="MathJax-Element-7-Frame">
            <span class="math" id="MathJax-Span-42">
             <span class="mrow" id="MathJax-Span-43">
              <span class="msubsup" id="MathJax-Span-44">
               <span class="mi" id="MathJax-Span-45">
                a
               </span>
               <span class="mn" id="MathJax-Span-46">
                1
               </span>
              </span>
             </span>
            </span>
           </span>
          </td>
          <td align="right">
           <span class="MathJax" id="MathJax-Element-8-Frame">
            <span class="math" id="MathJax-Span-47">
             <span class="mrow" id="MathJax-Span-48">
              <span class="msubsup" id="MathJax-Span-49">
               <span class="mi" id="MathJax-Span-50">
                a
               </span>
               <span class="mn" id="MathJax-Span-51">
                2
               </span>
              </span>
             </span>
            </span>
           </span>
          </td>
          <td align="right">
           …
          </td>
          <td align="right">
           <span class="MathJax" id="MathJax-Element-9-Frame">
            <span class="math" id="MathJax-Span-52">
             <span class="mrow" id="MathJax-Span-53">
              <span class="msubsup" id="MathJax-Span-54">
               <span class="mi" id="MathJax-Span-55">
                a
               </span>
               <span class="mi" id="MathJax-Span-56">
                n
               </span>
              </span>
             </span>
            </span>
           </span>
           ]
          </td>
         </tr>
         <tr>
          <td>
           output
          </td>
          <td align="center">
           [
           <span class="MathJax" id="MathJax-Element-10-Frame">
            <span class="math" id="MathJax-Span-57">
             <span class="mrow" id="MathJax-Span-58">
              <span class="mi" id="MathJax-Span-59">
               I
              </span>
             </span>
            </span>
           </span>
          </td>
          <td align="right">
           <span class="MathJax" id="MathJax-Element-11-Frame">
            <span class="math" id="MathJax-Span-60">
             <span class="mrow" id="MathJax-Span-61">
              <span class="msubsup" id="MathJax-Span-62">
               <span class="mi" id="MathJax-Span-63">
                a
               </span>
               <span class="mn" id="MathJax-Span-64">
                0
               </span>
              </span>
             </span>
            </span>
           </span>
          </td>
          <td align="right">
           <span class="MathJax" id="MathJax-Element-12-Frame">
            <span class="math" id="MathJax-Span-65">
             <span class="mrow" id="MathJax-Span-66">
              <span class="msubsup" id="MathJax-Span-67">
               <span class="mi" id="MathJax-Span-68">
                a
               </span>
               <span class="mn" id="MathJax-Span-69">
                0
               </span>
              </span>
              <span class="mo" id="MathJax-Span-70">
               ⨂
              </span>
              <span class="msubsup" id="MathJax-Span-71">
               <span class="mi" id="MathJax-Span-72">
                a
               </span>
               <span class="mn" id="MathJax-Span-73">
                1
               </span>
              </span>
             </span>
            </span>
           </span>
          </td>
          <td align="right">
           …
          </td>
          <td align="right">
           <span class="MathJax" id="MathJax-Element-13-Frame">
            <span class="math" id="MathJax-Span-74">
             <span class="mrow" id="MathJax-Span-75">
              <span class="msubsup" id="MathJax-Span-76">
               <span class="mi" id="MathJax-Span-77">
                a
               </span>
               <span class="mn" id="MathJax-Span-78">
                0
               </span>
              </span>
              <span class="mo" id="MathJax-Span-79">
               ⨂
              </span>
              <span class="msubsup" id="MathJax-Span-80">
               <span class="mi" id="MathJax-Span-81">
                a
               </span>
               <span class="mn" id="MathJax-Span-82">
                1
               </span>
              </span>
              <span class="mo" id="MathJax-Span-83">
               ⨂
              </span>
             </span>
            </span>
           </span>
           …
           <span class="MathJax" id="MathJax-Element-14-Frame">
            <span class="math" id="MathJax-Span-84">
             <span class="mrow" id="MathJax-Span-85">
              <span class="mo" id="MathJax-Span-86">
               ⨂
              </span>
              <span class="msubsup" id="MathJax-Span-87">
               <span class="mi" id="MathJax-Span-88">
                a
               </span>
               <span class="mi" id="MathJax-Span-89">
                n
               </span>
              </span>
             </span>
            </span>
           </span>
           ]
          </td>
         </tr>
        </tbody>
       </table>
       <p>
        其中
        <span class="MathJax" id="MathJax-Element-15-Frame">
         <span class="math" id="MathJax-Span-90">
          <span class="mrow" id="MathJax-Span-91">
           <span class="mo" id="MathJax-Span-92">
            ⨂
           </span>
          </span>
         </span>
        </span>
        是scan operator，I 是
        <span class="MathJax" id="MathJax-Element-16-Frame">
         <span class="math" id="MathJax-Span-93">
          <span class="mrow" id="MathJax-Span-94">
           <span class="mo" id="MathJax-Span-95">
            ⨂
           </span>
          </span>
         </span>
        </span>
        的identity element
       </p>
       <hr/>
       <p>
       </p>
       <h4 id="321-serial-implementation-of-scan">
        <p name="t8">
        </p>
        <strong>
         3.2.1 Serial implementation of Scan
        </strong>
       </h4>
       <p>
        很简单：
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7260234870126" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          int acc = identity;
&lt;span class="hljs-keyword"&gt;for&lt;/span&gt;(&lt;span class="hljs-built_in"&gt;i&lt;/span&gt;=&lt;span class="hljs-number"&gt;0&lt;/span&gt;;&lt;span class="hljs-built_in"&gt;i&lt;/span&gt;&amp;lt;&lt;span class="hljs-transposed_variable"&gt;elements.&lt;/span&gt;&lt;span class="hljs-built_in"&gt;length&lt;/span&gt;();&lt;span class="hljs-built_in"&gt;i&lt;/span&gt;++)&lt;span class="hljs-cell"&gt;{
    acc = acc op elements[i];
    out[i] = acc;
}&lt;/span&gt;
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7260234870126-1">
               1
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7260234870126-2">
               2
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7260234870126-3">
               3
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7260234870126-4">
               4
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7260234870126-5">
               5
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7260234870126-1">
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                acc
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                identity
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7260234870126-2">
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                for
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;=
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-transposed_variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                elements
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                length
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                ++
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-cell"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7260234870126-3">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                acc
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                acc
               </span>
               <span class="crayon-e">
                op
               </span>
               <span class="crayon-v">
                elements
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7260234870126-4">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                out
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                acc
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7260234870126-5">
               <span class="crayon-sy">
                }
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0051 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
        <li>
         2
        </li>
        <li>
         3
        </li>
        <li>
         4
        </li>
        <li>
         5
        </li>
       </ul>
       <p>
        work complexity:
        <span style="color: #efcf00;">
         <span class="MathJax" id="MathJax-Element-17-Frame">
          <span class="math" id="MathJax-Span-96">
           <span class="mrow" id="MathJax-Span-97">
            <span class="mi" id="MathJax-Span-98">
             O
            </span>
            <span class="mo" id="MathJax-Span-99">
             (
            </span>
            <span class="mi" id="MathJax-Span-100">
             n
            </span>
            <span class="mo" id="MathJax-Span-101">
             )
            </span>
           </span>
          </span>
         </span>
        </span>
        <br/>
        step complexity:
        <span style="color: #efcf00;">
         <span class="MathJax" id="MathJax-Element-18-Frame">
          <span class="math" id="MathJax-Span-102">
           <span class="mrow" id="MathJax-Span-103">
            <span class="mi" id="MathJax-Span-104">
             O
            </span>
            <span class="mo" id="MathJax-Span-105">
             (
            </span>
            <span class="mi" id="MathJax-Span-106">
             n
            </span>
            <span class="mo" id="MathJax-Span-107">
             )
            </span>
           </span>
          </span>
         </span>
        </span>
       </p>
       <p>
        那么，对于scan问题，我们怎样对其进行并行化呢？
       </p>
       <p>
       </p>
       <h4 id="321-parallel-implementation-of-scan">
        <p name="t9">
        </p>
        <strong>
         3.2.1 Parallel implementation of Scan
        </strong>
       </h4>
       <p>
        考虑scan的并行化，可以并行计算n个output，每个output元素i相当于
        <span class="MathJax" id="MathJax-Element-19-Frame">
         <span class="math" id="MathJax-Span-108">
          <span class="mrow" id="MathJax-Span-109">
           <span class="msubsup" id="MathJax-Span-110">
            <span class="mi" id="MathJax-Span-111">
             a
            </span>
            <span class="mn" id="MathJax-Span-112">
             0
            </span>
           </span>
           <span class="mo" id="MathJax-Span-113">
            ⨂
           </span>
           <span class="msubsup" id="MathJax-Span-114">
            <span class="mi" id="MathJax-Span-115">
             a
            </span>
            <span class="mn" id="MathJax-Span-116">
             1
            </span>
           </span>
           <span class="mo" id="MathJax-Span-117">
            ⨂
           </span>
          </span>
         </span>
        </span>
        …
        <span class="MathJax" id="MathJax-Element-20-Frame">
         <span class="math" id="MathJax-Span-118">
          <span class="mrow" id="MathJax-Span-119">
           <span class="mo" id="MathJax-Span-120">
            ⨂
           </span>
           <span class="msubsup" id="MathJax-Span-121">
            <span class="mi" id="MathJax-Span-122">
             a
            </span>
            <span class="mi" id="MathJax-Span-123">
             i
            </span>
           </span>
          </span>
         </span>
        </span>
        ，是一个reduce operation。
       </p>
       <p>
        Q: 那么问题的work complexity和step complexity分别变为多少了呢？
        <br/>
        Ans:
       </p>
       <ul>
        <li>
         step complexity:
         <br/>
         取决于n个reduction中耗时最长的，即
         <span class="MathJax" id="MathJax-Element-21-Frame">
          <span class="math" id="MathJax-Span-124">
           <span class="mrow" id="MathJax-Span-125">
            <span class="mi" id="MathJax-Span-126">
             O
            </span>
            <span class="mo" id="MathJax-Span-127">
             (
            </span>
            <span class="mi" id="MathJax-Span-128">
             l
            </span>
            <span class="mi" id="MathJax-Span-129">
             o
            </span>
            <span class="msubsup" id="MathJax-Span-130">
             <span class="mi" id="MathJax-Span-131">
              g
             </span>
             <span class="mn" id="MathJax-Span-132">
              2
             </span>
            </span>
            <span class="mi" id="MathJax-Span-133">
             n
            </span>
            <span class="mo" id="MathJax-Span-134">
             )
            </span>
           </span>
          </span>
         </span>
        </li>
        <li>
         work complexity:
         <br/>
         对于每个output元素进行计算，总计算量为0+1+2+…+(n-1)，所以复杂度为
         <span class="MathJax" id="MathJax-Element-22-Frame">
          <span class="math" id="MathJax-Span-135">
           <span class="mrow" id="MathJax-Span-136">
            <span class="mi" id="MathJax-Span-137">
             O
            </span>
            <span class="mo" id="MathJax-Span-138">
             (
            </span>
            <span class="msubsup" id="MathJax-Span-139">
             <span class="mi" id="MathJax-Span-140">
              n
             </span>
             <span class="mn" id="MathJax-Span-141">
              2
             </span>
            </span>
            <span class="mo" id="MathJax-Span-142">
             )
            </span>
           </span>
          </span>
         </span>
         .
        </li>
       </ul>
       <p>
        <span style="color: #00bfff;">
         可见，step complexity降下来了，可惜work complexity上去了
        </span>
        ，那么怎么解决呢？这里有两种Scan算法：
       </p>
       <table align="center" border="1">
        <tbody>
         <tr>
          <td>
          </td>
          <td>
           more step efficiency
          </td>
          <td>
           more work efficiency
          </td>
         </tr>
         <tr>
          <td align="center">
           hillis + steele （1986）
          </td>
          <td align="center">
           √
          </td>
          <td>
          </td>
         </tr>
         <tr>
          <td align="center">
           blelloch （1990）
          </td>
          <td>
          </td>
          <td align="center">
           √
          </td>
         </tr>
        </tbody>
       </table>
       <p>
       </p>
       <hr/>
       <ol>
        <li>
         <strong>
          Hillis + Steele
         </strong>
         <p>
          对于Scan加法问题，hillis+steele算法的解决方案如下：
         </p>
        </li>
       </ol>
       <p>
        <img src="http://img.blog.csdn.net/20150205192536172"/>
       </p>
       <p>
        即streaming’s
        <br/>
        step 0: out[i] = in[i] + in[i-1];
        <br/>
        step 1: out[i] = in[i] + in[i-2];
        <br/>
        step 2: out[i] = in[i] + in[i-4];
        <br/>
        如果元素不存在（向下越界）就记为0；可见step 2的output就是scan 加法的结果(想想为什么，我们一会再分析)。
       </p>
       <p>
        那么问题来了。。。
        <br/>
        Q: hillis + steele算法的work complexity 和 step complexity分别为多少？
       </p>
       <table align="center" border="1">
        <caption>
         Hillis + steele Algorithm complexity
        </caption>
        <tbody>
         <tr>
          <td>
          </td>
          <td>
           <span class="MathJax" id="MathJax-Element-23-Frame">
            <span class="math" id="MathJax-Span-143">
             <span class="mrow" id="MathJax-Span-144">
              <span class="mi" id="MathJax-Span-145">
               l
              </span>
              <span class="mi" id="MathJax-Span-146">
               o
              </span>
              <span class="mi" id="MathJax-Span-147">
               g
              </span>
              <span class="mo" id="MathJax-Span-148">
               (
              </span>
              <span class="mi" id="MathJax-Span-149">
               n
              </span>
              <span class="mo" id="MathJax-Span-150">
               )
              </span>
             </span>
            </span>
           </span>
          </td>
          <td>
           <span class="MathJax" id="MathJax-Element-24-Frame">
            <span class="math" id="MathJax-Span-151">
             <span class="mrow" id="MathJax-Span-152">
              <span class="mi" id="MathJax-Span-153">
               O
              </span>
              <span class="mo" id="MathJax-Span-154">
               (
              </span>
              <span class="msqrt" id="MathJax-Span-155">
               <span class="mrow" id="MathJax-Span-156">
                <span class="mi" id="MathJax-Span-157">
                 n
                </span>
               </span>
               √
              </span>
              <span class="mo" id="MathJax-Span-158">
               )
              </span>
             </span>
            </span>
           </span>
          </td>
          <td>
           <span class="MathJax" id="MathJax-Element-25-Frame">
            <span class="math" id="MathJax-Span-159">
             <span class="mrow" id="MathJax-Span-160">
              <span class="mi" id="MathJax-Span-161">
               O
              </span>
              <span class="mo" id="MathJax-Span-162">
               (
              </span>
              <span class="mi" id="MathJax-Span-163">
               n
              </span>
              <span class="mo" id="MathJax-Span-164">
               )
              </span>
             </span>
            </span>
           </span>
          </td>
          <td>
           <span class="MathJax" id="MathJax-Element-26-Frame">
            <span class="math" id="MathJax-Span-165">
             <span class="mrow" id="MathJax-Span-166">
              <span class="mi" id="MathJax-Span-167">
               O
              </span>
              <span class="mo" id="MathJax-Span-168">
               (
              </span>
              <span class="mi" id="MathJax-Span-169">
               n
              </span>
              <span class="mi" id="MathJax-Span-170">
               l
              </span>
              <span class="mi" id="MathJax-Span-171">
               o
              </span>
              <span class="mi" id="MathJax-Span-172">
               g
              </span>
              <span class="mi" id="MathJax-Span-173">
               n
              </span>
              <span class="mo" id="MathJax-Span-174">
               )
              </span>
             </span>
            </span>
           </span>
          </td>
          <td>
           O(n^2)
          </td>
         </tr>
         <tr>
          <td>
           work complexity
          </td>
          <td>
          </td>
          <td>
          </td>
          <td>
          </td>
          <td align="center">
           <span style="color: #ffffee; font-family: Verdana; font-size: small;">
            √
           </span>
          </td>
          <td>
          </td>
         </tr>
         <tr>
          <td>
           step complexity
          </td>
          <td align="center">
           <span style="color: #ffffee; font-family: Verdana; font-size: small;">
            √
           </span>
          </td>
          <td>
          </td>
          <td>
          </td>
          <td>
          </td>
          <td>
          </td>
         </tr>
        </tbody>
       </table>
       <p>
        解释：
       </p>
       <p>
        为了不妨碍大家思路，我在表格中将答案设为了白色，选中表格可见答案。
       </p>
       <ol>
        <li>
         step complexity：
         <br/>
         因为第i个step的结果为上一步输出作为in, out[idx] = in[idx] + in[idx – 2^i], 所以step complexity =
         <span class="MathJax" id="MathJax-Element-27-Frame">
          <span class="math" id="MathJax-Span-175">
           <span class="mrow" id="MathJax-Span-176">
            <span class="mi" id="MathJax-Span-177">
             O
            </span>
            <span class="mo" id="MathJax-Span-178">
             (
            </span>
            <span class="mi" id="MathJax-Span-179">
             l
            </span>
            <span class="mi" id="MathJax-Span-180">
             o
            </span>
            <span class="mi" id="MathJax-Span-181">
             g
            </span>
            <span class="mo" id="MathJax-Span-182">
             (
            </span>
            <span class="mi" id="MathJax-Span-183">
             n
            </span>
            <span class="mo" id="MathJax-Span-184">
             )
            </span>
            <span class="mo" id="MathJax-Span-185">
             )
            </span>
           </span>
          </span>
         </span>
        </li>
        <li>
         work complexity:
         <br/>
         workload =
         <span class="MathJax" id="MathJax-Element-28-Frame">
          <span class="math" id="MathJax-Span-186">
           <span class="mrow" id="MathJax-Span-187">
            <span class="mo" id="MathJax-Span-188">
             (
            </span>
            <span class="mi" id="MathJax-Span-189">
             n
            </span>
            <span class="mo" id="MathJax-Span-190">
             −
            </span>
            <span class="mn" id="MathJax-Span-191">
             1
            </span>
            <span class="mo" id="MathJax-Span-192">
             )
            </span>
            <span class="mo" id="MathJax-Span-193">
             +
            </span>
            <span class="mo" id="MathJax-Span-194">
             (
            </span>
            <span class="mi" id="MathJax-Span-195">
             n
            </span>
            <span class="mo" id="MathJax-Span-196">
             −
            </span>
            <span class="mn" id="MathJax-Span-197">
             2
            </span>
            <span class="mo" id="MathJax-Span-198">
             )
            </span>
            <span class="mo" id="MathJax-Span-199">
             +
            </span>
            <span class="mo" id="MathJax-Span-200">
             (
            </span>
            <span class="mi" id="MathJax-Span-201">
             n
            </span>
            <span class="mo" id="MathJax-Span-202">
             −
            </span>
            <span class="mn" id="MathJax-Span-203">
             4
            </span>
            <span class="mo" id="MathJax-Span-204">
             )
            </span>
            <span class="mo" id="MathJax-Span-205">
             +
            </span>
            <span class="mo" id="MathJax-Span-206">
             .
            </span>
            <span class="mo" id="MathJax-Span-207">
             .
            </span>
            <span class="mo" id="MathJax-Span-208">
             .
            </span>
           </span>
          </span>
         </span>
         ，共有
         <span class="MathJax" id="MathJax-Element-29-Frame">
          <span class="math" id="MathJax-Span-209">
           <span class="mrow" id="MathJax-Span-210">
            <span class="mi" id="MathJax-Span-211">
             l
            </span>
            <span class="mi" id="MathJax-Span-212">
             o
            </span>
            <span class="mi" id="MathJax-Span-213">
             g
            </span>
            <span class="mo" id="MathJax-Span-214">
             (
            </span>
            <span class="mi" id="MathJax-Span-215">
             n
            </span>
            <span class="mo" id="MathJax-Span-216">
             )
            </span>
           </span>
          </span>
         </span>
         项元素相加，所以可以近似看做一个矩阵，对应上图，长
         <span class="MathJax" id="MathJax-Element-30-Frame">
          <span class="math" id="MathJax-Span-217">
           <span class="mrow" id="MathJax-Span-218">
            <span class="mi" id="MathJax-Span-219">
             l
            </span>
            <span class="mi" id="MathJax-Span-220">
             o
            </span>
            <span class="mi" id="MathJax-Span-221">
             g
            </span>
            <span class="mo" id="MathJax-Span-222">
             (
            </span>
            <span class="mi" id="MathJax-Span-223">
             n
            </span>
            <span class="mo" id="MathJax-Span-224">
             )
            </span>
           </span>
          </span>
         </span>
         , 宽n，所以复杂度为
         <span class="MathJax" id="MathJax-Element-31-Frame">
          <span class="math" id="MathJax-Span-225">
           <span class="mrow" id="MathJax-Span-226">
            <span class="mi" id="MathJax-Span-227">
             n
            </span>
            <span class="mi" id="MathJax-Span-228">
             l
            </span>
            <span class="mi" id="MathJax-Span-229">
             o
            </span>
            <span class="mi" id="MathJax-Span-230">
             g
            </span>
            <span class="mo" id="MathJax-Span-231">
             (
            </span>
            <span class="mi" id="MathJax-Span-232">
             n
            </span>
            <span class="mo" id="MathJax-Span-233">
             )
            </span>
           </span>
          </span>
         </span>
         。
        </li>
       </ol>
       <p>
       </p>
       <hr/>
       <p>
        2 .
        <strong>
         Blelloch
        </strong>
       </p>
       <p>
        基本思路：Reduce + downsweep
       </p>
       <p>
        还是先讲做法。我们来看Blelloch算法的具体流程，分为reduce和downsweep 两部分，如图所示。
       </p>
       <p>
        <img src="http://img.blog.csdn.net/20150206182246335"/>
       </p>
       <p>
       </p>
       <ol>
        <li>
         reduce部分：
         <br/>
         每个step对相邻两个元素进行求和，但是每个元素在input中只出现一次，即window size=2, step = 2的求和。
         <br/>
         Q: reduce部分的step complexity 和 work complexity？
         <br/>
         Ans：
         <p>
         </p>
         <table align="center" border="1">
          <caption>
           Reduce part in Blelloch
          </caption>
          <tbody>
           <tr>
            <td>
            </td>
            <td>
             <span class="MathJax" id="MathJax-Element-32-Frame">
              <span class="math" id="MathJax-Span-234">
               <span class="mrow" id="MathJax-Span-235">
                <span class="mi" id="MathJax-Span-236">
                 l
                </span>
                <span class="mi" id="MathJax-Span-237">
                 o
                </span>
                <span class="mi" id="MathJax-Span-238">
                 g
                </span>
                <span class="mo" id="MathJax-Span-239">
                 (
                </span>
                <span class="mi" id="MathJax-Span-240">
                 n
                </span>
                <span class="mo" id="MathJax-Span-241">
                 )
                </span>
               </span>
              </span>
             </span>
            </td>
            <td>
             <span class="MathJax" id="MathJax-Element-33-Frame">
              <span class="math" id="MathJax-Span-242">
               <span class="mrow" id="MathJax-Span-243">
                <span class="mi" id="MathJax-Span-244">
                 O
                </span>
                <span class="mo" id="MathJax-Span-245">
                 (
                </span>
                <span class="msqrt" id="MathJax-Span-246">
                 <span class="mrow" id="MathJax-Span-247">
                  <span class="mi" id="MathJax-Span-248">
                   n
                  </span>
                 </span>
                 √
                </span>
                <span class="mo" id="MathJax-Span-249">
                 )
                </span>
               </span>
              </span>
             </span>
            </td>
            <td>
             <span class="MathJax" id="MathJax-Element-34-Frame">
              <span class="math" id="MathJax-Span-250">
               <span class="mrow" id="MathJax-Span-251">
                <span class="mi" id="MathJax-Span-252">
                 O
                </span>
                <span class="mo" id="MathJax-Span-253">
                 (
                </span>
                <span class="mi" id="MathJax-Span-254">
                 n
                </span>
                <span class="mo" id="MathJax-Span-255">
                 )
                </span>
               </span>
              </span>
             </span>
            </td>
            <td>
             <span class="MathJax" id="MathJax-Element-35-Frame">
              <span class="math" id="MathJax-Span-256">
               <span class="mrow" id="MathJax-Span-257">
                <span class="mi" id="MathJax-Span-258">
                 O
                </span>
                <span class="mo" id="MathJax-Span-259">
                 (
                </span>
                <span class="mi" id="MathJax-Span-260">
                 n
                </span>
                <span class="mi" id="MathJax-Span-261">
                 l
                </span>
                <span class="mi" id="MathJax-Span-262">
                 o
                </span>
                <span class="mi" id="MathJax-Span-263">
                 g
                </span>
                <span class="mi" id="MathJax-Span-264">
                 n
                </span>
                <span class="mo" id="MathJax-Span-265">
                 )
                </span>
               </span>
              </span>
             </span>
            </td>
            <td>
             O(n^2)
            </td>
           </tr>
           <tr>
            <td>
             work complexity
            </td>
            <td>
            </td>
            <td>
            </td>
            <td align="center">
             <span style="color: #ffffee; font-family: Verdana; font-size: small;">
              √
             </span>
            </td>
            <td>
            </td>
            <td>
            </td>
           </tr>
           <tr>
            <td>
             step complexity
            </td>
            <td align="center">
             <span style="color: #ffffee; font-family: Verdana; font-size: small;">
              √
             </span>
            </td>
            <td>
            </td>
            <td>
            </td>
            <td>
            </td>
            <td>
            </td>
           </tr>
          </tbody>
         </table>
         <p>
          我们依然将答案用白色标出，请选中看答案。
         </p>
        </li>
        <li>
         downsweep部分：
         <br/>
         简单地说，downsweep部分的输入元素是reduce部分镜面反射的结果，对于每一组输入in1 &amp; in2有两个输出，左边输出out1 = in2，右边输出out2 = in1 op in2 （这里的op就是reduce部分的op），如图：
        </li>
       </ol>
       <p>
       </p>
       <center>
        <br/>
        <img src="http://img.blog.csdn.net/20150206175501329"/>
       </center>
       如上上图中的op为加法，那举个例子就有：in1 = 11, in2 = 10, 可得out1 = in2 = 10， out2 = in1 + in2 = 21。由此可以推出downsweep部分的所有value，如上上图。
       <br/>
       这里画圈的元素都是从reduce部分直接“天降”（镜面反射）过来的，注意，每一个元素位置只去reduce出来该位置的最终结果，而且由于是镜面反射，step层数越大的reduce计算结果“天降”越快，即从reduce的“天降”顺序为
       <p>
       </p>
       <table align="center">
        <tbody>
         <tr>
          <td>
           36
          </td>
         </tr>
         <tr>
          <td>
           10
          </td>
         </tr>
         <tr>
          <td>
           3, 11
          </td>
         </tr>
         <tr>
          <td>
           1, 3, 5, 7
          </td>
         </tr>
        </tbody>
       </table>
       <p>
        Q: downsweep部分的step complexity 和 work complexity？
        <br/>
        And：downsweep是reduce部分的mirror，所以当然和reduce部分的complexity都一样啦。
       </p>
       <p>
        <span style="color: red;">
         综上，Blelloch方法的work complexity为
         <span class="MathJax" id="MathJax-Element-36-Frame">
          <span class="math" id="MathJax-Span-266">
           <span class="mrow" id="MathJax-Span-267">
            <span class="mi" id="MathJax-Span-268">
             O
            </span>
            <span class="mo" id="MathJax-Span-269">
             (
            </span>
            <span class="mi" id="MathJax-Span-270">
             n
            </span>
            <span class="mo" id="MathJax-Span-271">
             )
            </span>
           </span>
          </span>
         </span>
         ，step 数为
         <span class="MathJax" id="MathJax-Element-37-Frame">
          <span class="math" id="MathJax-Span-272">
           <span class="mrow" id="MathJax-Span-273">
            <span class="mn" id="MathJax-Span-274">
             2
            </span>
            <span class="mo" id="MathJax-Span-275">
             ⋅
            </span>
            <span class="mi" id="MathJax-Span-276">
             l
            </span>
            <span class="mi" id="MathJax-Span-277">
             o
            </span>
            <span class="mi" id="MathJax-Span-278">
             g
            </span>
            <span class="mo" id="MathJax-Span-279">
             (
            </span>
            <span class="mi" id="MathJax-Span-280">
             n
            </span>
            <span class="mo" id="MathJax-Span-281">
             )
            </span>
           </span>
          </span>
         </span>
         .
        </span>
        这里我们可以看出相比于Hillis + Steele方法，Blelloch的总工作量更小。那么问题来了，这两种方法
        <span style="color: #30bada;">
         哪个更快呢？
        </span>
       </p>
       <p>
        ANS：这取决于所用的GPU，问题规模，以及实现时的优化方法。这一边是一个不断变化的问题：一开始我们有很多data（work &gt; processor）, 更适合用work efficient parallel algorithm (e.g Blelloch), 随着程序运行，工作量被减少了（processor &gt; work），适合改用step efficient parallel algorithm，这样而后数据又多起来啦，于是我们又适合用work efficient parallel algorithm…
       </p>
       <hr/>
       <p>
        总结一下，见下表为每种方法的complexity，以及适于解决的问题：
       </p>
       <table align="center" border="1">
        <tbody>
         <tr>
          <td>
          </td>
          <td>
           serial
          </td>
          <td>
           Hillis + Steele
          </td>
          <td>
           Blelloch
          </td>
         </tr>
         <tr>
          <td>
           work
          </td>
          <td align="center">
           O(n)
          </td>
          <td align="center">
           O(nlogn)
          </td>
          <td align="center">
           O(n)
          </td>
         </tr>
         <tr>
          <td>
           step
          </td>
          <td align="center">
           n
          </td>
          <td align="center">
           log(n)
          </td>
          <td align="center">
           2*log(n)
          </td>
         </tr>
         <tr>
          <td>
           512个元素的vector
           <br/>
           512个processor
          </td>
          <td>
          </td>
          <td align="center">
           √
          </td>
          <td>
          </td>
         </tr>
         <tr>
          <td>
           一百万的vector
           <br/>
           512个processor
          </td>
          <td>
          </td>
          <td>
          </td>
          <td align="center">
           √
          </td>
         </tr>
         <tr>
          <td>
           128k的vector
           <br/>
           1个processor
          </td>
          <td align="center">
           √
          </td>
          <td>
          </td>
          <td>
          </td>
         </tr>
        </tbody>
       </table>
       <hr/>
       <p>
       </p>
       <h2 id="4-histogram">
        <p name="t10">
        </p>
        4. Histogram
       </h2>
       <h3 id="41-what-is-histogram">
        <p name="t11">
        </p>
        4.1. what is histogram?
       </h3>
       <p>
        顾名思义，统计直方图就是将一个统计量在直方图中显示出来。
       </p>
       <h3 id="42-histogram-的-serial-实现">
        <p name="t12">
        </p>
        4.2. Histogram 的 Serial 实现：
       </h3>
       <p>
        分两部分：1. 初始化，2. 统计
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7278676852484" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          &lt;span class="hljs-keyword"&gt;for&lt;/span&gt;(&lt;span class="hljs-built_in"&gt;i&lt;/span&gt; = &lt;span class="hljs-number"&gt;0&lt;/span&gt;; &lt;span class="hljs-built_in"&gt;i&lt;/span&gt; &amp;lt; &lt;span class="hljs-transposed_variable"&gt;bin.&lt;/span&gt;count; &lt;span class="hljs-built_in"&gt;i&lt;/span&gt;++)
    res&lt;span class="hljs-matrix"&gt;[i]&lt;/span&gt; = &lt;span class="hljs-number"&gt;0&lt;/span&gt;;
&lt;span class="hljs-keyword"&gt;for&lt;/span&gt;(&lt;span class="hljs-built_in"&gt;i&lt;/span&gt; = &lt;span class="hljs-number"&gt;0&lt;/span&gt;; &lt;span class="hljs-built_in"&gt;i&lt;/span&gt;&amp;lt;nElements; &lt;span class="hljs-built_in"&gt;i&lt;/span&gt;++)
    res&lt;span class="hljs-matrix"&gt;[computeBin(i)]&lt;/span&gt; ++;
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7278676852484-1">
               1
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7278676852484-2">
               2
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7278676852484-3">
               3
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7278676852484-4">
               4
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7278676852484-1">
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                for
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-transposed_variable"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                bin
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                count
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                ++
               </span>
               <span class="crayon-sy">
                )
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7278676852484-2">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                res
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-matrix"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7278676852484-3">
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                for
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-number"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-cn">
                0
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                &amp;
               </span>
               <span class="crayon-v">
                lt
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-v">
                nElements
               </span>
               <span class="crayon-sy">
                ;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-built_in"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                ++
               </span>
               <span class="crayon-sy">
                )
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7278676852484-4">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                res
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-matrix"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-e">
                computeBin
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-v">
                i
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                ++
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0071 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
        <li>
         2
        </li>
        <li>
         3
        </li>
        <li>
         4
        </li>
       </ul>
       <h3 id="43-histogram-的-parallel-实现">
        <p name="t13">
        </p>
        4.3. Histogram 的 Parallel 实现：
       </h3>
       <ol>
        <li>
         直接实现：
        </li>
       </ol>
       <p>
        kernel:
       </p>
       <!-- Crayon Syntax Highlighter v_2.7.2_beta -->
       <div class="crayon-syntax crayon-theme-classic crayon-font-monaco crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover" id="crayon-57685288b7280457781869" style=" margin-top: 12px; margin-bottom: 12px; font-size: 12px !important; line-height: 15px !important;">
        <div class="crayon-toolbar" data-settings=" mouseover overlay hide delay" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
         <span class="crayon-title">
         </span>
         <div class="crayon-tools" style="font-size: 12px !important;height: 18px !important; line-height: 18px !important;">
          <div class="crayon-button crayon-nums-button" title="切换是否显示行编号">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-plain-button" title="纯文本显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-wrap-button" title="切换自动换行">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-expand-button" title="点击展开代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-copy-button" title="复制代码">
           <div class="crayon-button-icon">
           </div>
          </div>
          <div class="crayon-button crayon-popup-button" title="在新窗口中显示代码">
           <div class="crayon-button-icon">
           </div>
          </div>
         </div>
        </div>
        <div class="crayon-info" style="min-height: 16.8px !important; line-height: 16.8px !important;">
        </div>
        <div class="crayon-plain-wrap">
         <textarea class="crayon-plain print-no" data-settings="dblclick" readonly="" style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 12px !important; line-height: 15px !important;" wrap="soft">
          __global__ &lt;span class="hljs-keyword"&gt;void&lt;/span&gt; naive_histo(&lt;span class="hljs-keyword"&gt;int&lt;/span&gt;* d_bins, &lt;span class="hljs-keyword"&gt;const&lt;/span&gt; &lt;span class="hljs-keyword"&gt;int&lt;/span&gt;* d_in, &lt;span class="hljs-keyword"&gt;const&lt;/span&gt; &lt;span class="hljs-keyword"&gt;in&lt;/span&gt; BIN_COUNT){
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; myID = threadIdx.x + blockDim.x * blockIdx.x;
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; myItem = d_in[myID];
    &lt;span class="hljs-keyword"&gt;int&lt;/span&gt; myBin = myItem % BIN_COUNT;
    d_bins[myBin]++;
}
         </textarea>
        </div>
        <div class="crayon-main" style="">
         <table class="crayon-table">
          <tbody>
           <tr class="crayon-row">
            <td class="crayon-nums " data-settings="show">
             <div class="crayon-nums-content" style="font-size: 12px !important; line-height: 15px !important;">
              <div class="crayon-num" data-line="crayon-57685288b7280457781869-1">
               1
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7280457781869-2">
               2
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7280457781869-3">
               3
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7280457781869-4">
               4
              </div>
              <div class="crayon-num" data-line="crayon-57685288b7280457781869-5">
               5
              </div>
              <div class="crayon-num crayon-striped-num" data-line="crayon-57685288b7280457781869-6">
               6
              </div>
             </div>
            </td>
            <td class="crayon-code">
             <div class="crayon-pre" style="font-size: 12px !important; line-height: 15px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;">
              <div class="crayon-line" id="crayon-57685288b7280457781869-1">
               <span class="crayon-v">
                __global__
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                void
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-e">
                naive_histo
               </span>
               <span class="crayon-sy">
                (
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_bins
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-m">
                const
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-o">
                *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                ,
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-m">
                const
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-st">
                in
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                BIN_COUNT
               </span>
               <span class="crayon-sy">
                )
               </span>
               <span class="crayon-sy">
                {
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7280457781869-2">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                threadIdx
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                +
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockDim
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-e ">
                x *
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                blockIdx
               </span>
               <span class="crayon-sy">
                .
               </span>
               <span class="crayon-v">
                x
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7280457781869-3">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                myItem
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_in
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myID
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7280457781869-4">
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-e">
                span
               </span>
               <span class="crayon-t">
                class
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-s">
                "hljs-keyword"
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-t">
                int
               </span>
               <span class="crayon-o">
                &lt;
               </span>
               <span class="crayon-o">
                /
               </span>
               <span class="crayon-v">
                span
               </span>
               <span class="crayon-o">
                &gt;
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                myBin
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                =
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                myItem
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-o">
                %
               </span>
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                BIN_COUNT
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line" id="crayon-57685288b7280457781869-5">
               <span class="crayon-h">
               </span>
               <span class="crayon-v">
                d_bins
               </span>
               <span class="crayon-sy">
                [
               </span>
               <span class="crayon-v">
                myBin
               </span>
               <span class="crayon-sy">
                ]
               </span>
               <span class="crayon-o">
                ++
               </span>
               <span class="crayon-sy">
                ;
               </span>
              </div>
              <div class="crayon-line crayon-striped-line" id="crayon-57685288b7280457781869-6">
               <span class="crayon-sy">
                }
               </span>
              </div>
             </div>
            </td>
           </tr>
          </tbody>
         </table>
        </div>
       </div>
       <!-- [Format Time: 0.0061 seconds] -->
       <p>
       </p>
       <ul class="pre-numbering">
        <li>
         1
        </li>
        <li>
         2
        </li>
        <li>
         3
        </li>
        <li>
         4
        </li>
        <li>
         5
        </li>
        <li>
         6
        </li>
       </ul>
       <p>
        来想想这样有什么问题？又是我们上次说的
        <span style="color: red;">
         read-modify-write
        </span>
        问题，而serial implementation不会有这个问题，那么想实现parallel histogram计算有什么方法呢？
       </p>
       <p>
        <strong>
         法1. accumulate using atomics
        </strong>
        <br/>
        即，将最后一句变成
        <br/>
        <code>
         atomicAdd(&amp;(d_bins[myBin]), 1);
        </code>
        <br/>
        但是对于atomics的方法而言，不管GPU多好，并行线程数都被限制到histogram个数N，也就是最多只有N个线程并行。
       </p>
       <p>
        <strong>
         法2. local memory + reduce
        </strong>
        <br/>
        设置n个并行线程，每个线程都有自己的local histogram（一个长为bin数的vector）；即每个local histogram都被一个thread顺序访问，所以这样没有shared memory，即便没有用atomics也不会出现read-modify-write问题。
        <br/>
        然后，我们将这n个histogram进行合并（即加和），可以通过reduce实现。
       </p>
       <p>
        <strong>
         法3. sort then reduce by key
        </strong>
        <br/>
        将数据组织成key-value对，key为histogram bin，value为1，即
       </p>
       <table align="center">
        <tbody>
         <tr>
          <td>
           key
          </td>
          <td>
           2
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           2
          </td>
          <td>
           1
          </td>
          <td>
           0
          </td>
          <td>
           2
          </td>
          <td>
           2
          </td>
         </tr>
         <tr>
          <td>
           value
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
         </tr>
        </tbody>
       </table>
       <p>
        将其按key排序，形成：
       </p>
       <table align="center">
        <tbody>
         <tr>
          <td>
           key
          </td>
          <td>
           0
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           2
          </td>
          <td>
           2
          </td>
          <td>
           2
          </td>
          <td>
           2
          </td>
         </tr>
         <tr>
          <td>
           value
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
          <td>
           1
          </td>
         </tr>
        </tbody>
       </table>
       <p>
        然后对相同key进行reduce求和，就可以得到histogram中的每个bin的总数。
       </p>
       <hr/>
       <p>
        综上，有三种实现paralle histogram的方法：
        <br/>
        1. atomics
        <br/>
        2. per_thread histogram, then reduce
        <br/>
        3. sort, then reduce by key
       </p>
       <hr/>
       <h2 id="5-总结">
        <p name="t14">
        </p>
        5. 总结：
       </h2>
       <p>
        本文介绍了三个gpu基础算法：reduce，scan和histogram的串行及并行实现，并巩固了之前讲过的gpu memory相关知识加以运用。
       </p>
      </div>
      <div>
       <strong>
        注：转载文章均来自于公开网络，仅供学习使用，不会用于任何商业用途，如果侵犯到原作者的权益，请您与我们联系删除或者授权事宜，联系邮箱：contact@dataunion.org。转载数盟网站文章请注明原文章作者，否则产生的任何版权纠纷与数盟无关。
       </strong>
      </div>
      <!--content_text-->
      <div class="fenxian">
       <!-- JiaThis Button BEGIN -->
       <div class="jiathis_style_32x32">
        <p class="jiathis_button_weixin">
        </p>
        <p class="jiathis_button_tsina">
        </p>
        <p class="jiathis_button_qzone">
        </p>
        <p class="jiathis_button_cqq">
        </p>
        <p class="jiathis_button_tumblr">
        </p>
        <a class="jiathis jiathis_txt jtico jtico_jiathis" href="http://www.jiathis.com/share" target="_blank">
        </a>
        <p class="jiathis_counter_style">
        </p>
       </div>
       <!-- JiaThis Button END -->
      </div>
     </article>
     <!--content-->
     <!--相关文章-->
     <div class="xianguan">
      <div class="xianguantitle">
       相关文章！
      </div>
      <ul class="pic">
       <li>
        <a href="http://dataunion.org/20824.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/t018630756a7e263b33-300x165.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20824.html" rel="bookmark" title="如何判断一笔交易是否属于欺诈？你只是需要一点数据挖掘">
         如何判断一笔交易是否属于欺诈？你只是需要一点数据挖掘
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/20820.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/1-300x200.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20820.html" rel="bookmark" title="人们对Python在企业级开发中的10大误解">
         人们对Python在企业级开发中的10大误解
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/20811.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/t0133fcacae8523307b_副本-300x200.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20811.html" rel="bookmark" title="大神亲传：26条深度学习的金科玉律！">
         大神亲传：26条深度学习的金科玉律！
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/20808.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/640.webp-11-300x137.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20808.html" rel="bookmark" title="我们是如何在一张地图上表现86万个数据的">
         我们是如何在一张地图上表现86万个数据的
        </a>
       </li>
      </ul>
     </div>
     <!--相关文章-->
     <div class="comment" id="comments">
      <!-- You can start editing here. -->
      <!-- If comments are open, but there are no comments. -->
      <div class="title">
       期待你一针见血的评论，Come on！
      </div>
      <div id="respond">
       <p>
        不用想啦，马上
        <a href="http://dataunion.org/wp-login.php?redirect_to=http%3A%2F%2Fdataunion.org%2F19959.html">
         "登录"
        </a>
        发表自已的想法.
       </p>
      </div>
     </div>
     <!-- .nav-single -->
    </div>
    <!--Container End-->
    <aside id="sitebar">
     <div class="sitebar_list2">
      <div class="wptag">
       <span class="tagtitle">
        热门标签+
       </span>
       <div class="tagg">
        <ul class="menu" id="menu-%e5%8f%8b%e6%83%85%e9%93%be%e6%8e%a5">
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-1605" id="menu-item-1605">
          <a href="http://taidizh.com/">
           泰迪智慧
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20884" id="menu-item-20884">
          <a href="http://www.transwarp.cn/">
           星环科技
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-3538" id="menu-item-3538">
          <a href="http://datall.org/">
           珈和遥感
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20888" id="menu-item-20888">
          <a href="http://www.chinahadoop.cn/">
           小象学院
          </a>
         </li>
        </ul>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <div class="textwidget">
       <div align="center">
        <a href="http://study.163.com/course/courseMain.htm?courseId=991022" target="_blank">
         <img src="http://dataunion.org/wp-content/uploads/2016/03/dv.jpg"/>
        </a>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       文章分类
      </h4>
      <div class="tagcloud">
       <a class="tag-link-44" href="http://dataunion.org/category/industry/demo" style="font-size: 10.204724409449pt;" title="4个话题">
        Demo展示
       </a>
       <a class="tag-link-31" href="http://dataunion.org/category/experts" style="font-size: 15.826771653543pt;" title="52个话题">
        专家团队
       </a>
       <a class="tag-link-870" href="http://dataunion.org/category/tech/ai" style="font-size: 19.795275590551pt;" title="273个话题">
        人工智能
       </a>
       <a class="tag-link-488" href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f" style="font-size: 8pt;" title="1个话题">
        加入数盟
       </a>
       <a class="tag-link-869" href="http://dataunion.org/category/tech/viz" style="font-size: 17.204724409449pt;" title="93个话题">
        可视化
       </a>
       <a class="tag-link-30" href="http://dataunion.org/category/partners" style="font-size: 10.645669291339pt;" title="5个话题">
        合作伙伴
       </a>
       <a class="tag-link-889" href="http://dataunion.org/category/parterc" style="font-size: 11.582677165354pt;" title="8个话题">
        合作会议
       </a>
       <a class="tag-link-104" href="http://dataunion.org/category/books" style="font-size: 12.96062992126pt;" title="15个话题">
        图书
       </a>
       <a class="tag-link-220" href="http://dataunion.org/category/tech/base" style="font-size: 19.850393700787pt;" title="281个话题">
        基础架构
       </a>
       <a class="tag-link-219" href="http://dataunion.org/category/tech/analysis" style="font-size: 19.409448818898pt;" title="232个话题">
        数据分析
       </a>
       <a class="tag-link-887" href="http://dataunion.org/category/tech/dm" style="font-size: 13.291338582677pt;" title="17个话题">
        数据挖掘
       </a>
       <a class="tag-link-34" href="http://dataunion.org/category/tech" style="font-size: 20.732283464567pt;" title="404个话题">
        文章
       </a>
       <a class="tag-link-1" href="http://dataunion.org/category/uncategorized" style="font-size: 22pt;" title="693个话题">
        未分类
       </a>
       <a class="tag-link-4" href="http://dataunion.org/category/events" style="font-size: 14.503937007874pt;" title="29个话题">
        活动
       </a>
       <a class="tag-link-890" href="http://dataunion.org/category/tech/%e6%b7%b1%e5%ba%a6%e5%ad%a6%e4%b9%a0" style="font-size: 10.204724409449pt;" title="4个话题">
        深度学习
       </a>
       <a class="tag-link-221" href="http://dataunion.org/category/tech/devl" style="font-size: 18.968503937008pt;" title="193个话题">
        编程语言
       </a>
       <a class="tag-link-888" href="http://dataunion.org/category/career" style="font-size: 15.661417322835pt;" title="48个话题">
        职业规划
       </a>
       <a class="tag-link-5" href="http://dataunion.org/category/jobs" style="font-size: 14.11811023622pt;" title="25个话题">
        职位
       </a>
       <a class="tag-link-871" href="http://dataunion.org/category/industry" style="font-size: 15.716535433071pt;" title="49个话题">
        行业
       </a>
       <a class="tag-link-613" href="http://dataunion.org/category/industry/case" style="font-size: 16.984251968504pt;" title="84个话题">
        行业应用
       </a>
       <a class="tag-link-885" href="http://dataunion.org/category/industry/news" style="font-size: 17.425196850394pt;" title="102个话题">
        行业资讯
       </a>
       <a class="tag-link-10" href="http://dataunion.org/category/training" style="font-size: 14.228346456693pt;" title="26个话题">
        课程
       </a>
       <a class="tag-link-16" href="http://dataunion.org/category/sources" style="font-size: 15.661417322835pt;" title="48个话题">
        资源
       </a>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       功能
      </h4>
      <ul>
       <li>
        <a href="http://dataunion.org/wp-login.php?action=register">
         注册
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/wp-login.php">
         登录
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/feed">
         文章
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/comments/feed">
         评论
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="https://cn.wordpress.org/" title="基于WordPress，一个优美、先进的个人信息发布平台。">
         WordPress.org
        </a>
       </li>
      </ul>
     </div>
    </aside>
    <div class="clear">
    </div>
   </div>
   <!--main-->
   ﻿
   <footer id="dibu">
    <div class="about">
     <div class="right">
      <ul class="menu" id="menu-%e5%ba%95%e9%83%a8%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-18024" id="menu-item-18024">
        <a href="http://dataunion.org/category/partners">
         合作伙伴
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20881" id="menu-item-20881">
        <a href="http://dataunion.org/contribute">
         文章投稿
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20872" id="menu-item-20872">
        <a href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f">
         加入数盟
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22441" id="menu-item-22441">
        <a href="http://dataunion.org/f-links">
         友情链接
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20874" id="menu-item-20874">
        <a href="http://dataunion.org/aboutus">
         关于数盟
        </a>
       </li>
      </ul>
      <p class="banquan">
       数盟社区        ，
        做最棒的数据科学社区
      </p>
     </div>
     <div class="left">
      <ul class="bottomlist">
       <li>
        <a href="http://weibo.com/DataScientistUnion  " target="_blank" 　title="">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weibo.png"/>
        </a>
       </li>
       <li>
        <a class="cd-popup-trigger" href="http://dataunion.org/19959.html#0">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weixin.png"/>
        </a>
       </li>
      </ul>
      <div class="cd-popup">
       <div class="cd-popup-container">
        <h1>
         扫描二维码,加微信公众号
        </h1>
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/2014-12-06-1515289049.png"/>
        <a class="cd-popup-close" href="http://dataunion.org/19959.html">
        </a>
       </div>
       <!-- cd-popup-container -->
      </div>
      <!-- cd-popup -->
     </div>
    </div>
    <!--about-->
    <div class="bottom">
     <a href="http://dataunion.org/">
      数盟社区
     </a>
     <a href="http://www.miitbeian.gov.cn/" rel="external nofollow" target="_blank">
      京ICP备14026740号
     </a>
     联系我们：
     <a href="mailto:contact@dataunion.org" target="_blank">
      contact@dataunion.org
     </a>
     <div class="tongji">
     </div>
     <!--bottom-->
     <div class="scroll" id="scroll" style="display:none;">
      ︿
     </div>
    </div>
   </footer>
   <!--dibu-->
  </div>
 </body>
</html>